Network topology discovery is the practice of mapping a network to discover a graph representing hosts (e.g. computer systems), network elements (e.g. routers or switches), and the various interconnections between them. Topology discovery can be at a variety of levels ranging from Internet-scale mapping efforts to small-scale home area networks. However, the techniques applicable to one effort are not necessarily transferable to others. Further, the amount of support for topology discovery provided by the network elements also varies. For example, network elements typically found in the home area provide minimal or no support, while enterprise Local Area Networks (LANs) usually include Simple Network Management Protocol (SNMP)-capable switches that allow their own knowledge about the topology of the network to be extracted using a remote management interface.
Knowledge of the network topology is useful for a variety of reasons, involving the computer systems themselves, direct users of computer systems, and support technicians. As a first example, computer systems attempting to carry media streams between them over a computer network can benefit from various schemes to do admission control, congestion avoidance and/or bandwidth adaptation in order to present the best quality media stream possible. In a general network formed from many network links and network elements, the bandwidth, congestion and usage of the links can be varied. It is generally accepted that schemes which attempt to monitor and adapt to network behavior provide better quality than those that do not. Any automated scheme of monitoring the network will be more easily constructed, or perform more accurate monitoring, if the organization (topology) of the network links is available to that scheme. Systems exist to analyze a link or path in the network; use of the topological information can lead to a more efficient analysis of the links and paths in the network. Likewise, if a computer system, or agent running on a computer system, is performing admission control of streams through some network element or network link on behalf of the streams of data packets wishing to use that network element or network link, such a system will act with greater information if the topological arrangement of the network links and network elements is known to it.
As a second example, the availability of network topology to users can benefit the level of troubleshooting which can be carried out, even by ordinary, untrained users. For example, if the computers attached to some network element become uncommunicative simultaneously, it is likely to be the network element that is at fault, rather than a correlated failure of the computer systems. Helpful fault diagnosis is particularly important in small office network environments and home network environments where it is unlikely that a dedicated support staff is available on site to resolve problems.
As a third example, where professional support staff is available, such as in an enterprise network environment, knowing the topology of the network is one of the key pieces used for operations, maintenance and troubleshooting. Software products exist that are designed to present the network topology to the enterprise administrator.
Previous work in the field of network topology discovery includes discovery schemes that can be characterized under a number of different classifications. For example, one classification is active or passive, which is directed towards whether the scheme requires the deliberate sending of additional traffic into the network in order to cause its topology to be discovered, or whether the topology can be discovered entirely passively from observation of real traffic naturally present in the network. Another classification is collaborative or non-collaborative, which is directed towards whether the computers attached to the network need to support the topology discovery process in some particular way (e.g., for them to be visible to the network topology), or whether the discovery process can proceed without their aid.
Other ways of classifying topology discovery are directed towards mapping layer, network support, and information properties. In general, one can associate a particular network topology with each communications layer. More particularly, communications systems are structured into multiple layers using concepts of abstraction in order to help deal with issues of complexity, each layer using the services of a lower layer. Topology discovery techniques may be applicable or discover only the structure of the network visible at some particular layer in this hierarchy. For example, the topology may operate at the layer of the Internet Protocol (IP), or at the Ethernet network (IEEE 802.3) layer.
Network support is generally directed toward determining whether the network elements (as distinct from the computers attached to the network) need to support an information protocol (such as the Simple Network Management Protocol (SNMP) or the Cisco Discovery Protocol (CDP)) in order to permit the topology to be discovered. Information properties are directed towards how much information is discovered about the links and elements in the network. For example, information properties consider whether connectivity is the only aspect discovered, or whether information about manufacturer, physical location (distinct from the logical location within the graph of the network), loss rate, error rate, bandwidth, delay or some other properties are discovered. It should be understood that many schemes begin with connectivity information alone and then use it to determine some of these other properties.
Recently, there has been some research into Internet-scale mapping, sometimes called tomography, which tend to be passive, non-collaborative protocols which map at the IP-layer. Mapping enterprise or data-center networks is often performed with commercial products such as IBM/Tivoli's NetView and Hewlett Packard's OpenView, as well as an SNMP software tool generally referred to as Nomad (Paul Coates, “Nomad: Network Mapping and Monitoring” an SNMP software tool distributed by Newcastle University, United Kingdom). In general, these systems work by issuing SNMP queries for Management Information Base (MIB) tables stored in routers, IEEE 802.1d Bridge MIBs, and RMON-2 MIBs (Remote Network Monitoring Management Information Base). These MIBs give information about the ports on the network element (IP router or Ethernet network switch), and include which hosts or other network elements are connected to these ports.
However these MIBs may only contain information on recently active hosts, since bridges timeout their port filtering tables after around five minutes. Also, properly secured network elements will need the mapping system to supply appropriate authentication (known in SNMP as a community string) before allowing access. Another feature of these management interfaces is that there is some variance in how they are implemented, although they are supposed to be standardized. Work-around techniques are needed to deal with these variances, as described in the publication by Bruce Lowekamp, David R. O'Hallaron and Thomas R. Gross, “Topology Discovery for Large Ethernet networks” in Proceedings of ACM SIGCOMM 2001. In general, the use of MIBs presents a fairly efficient technique for stitching together the partial topologies resulting from SNMP queries into a consistent whole, using contradictions to quickly narrow down the possible interconnections between switches.
A significant shortcoming with any of these known techniques is that in many cases, certain areas of networks have heretofore remained unmapped. One reason for this is that in many cases, no one has control over the hardware with respect to being able to automatically identify the equipment and its capabilities. Even if new standards are implemented with respect to hardware that does identify itself and its capabilities, there will still remain large quantities of legacy Ethernet network equipment in circulation. Moreover, inexpensive switches and hubs (e.g., for home networking or small business use) will likely never implement such complex behavior, due to it being too costly.